package com.lyz.dataStructure.JianZhiOffer;/**
 * @Author:759057893@qq.com Lyz
 * @Date: ${Date} 17:45
 * @Description:
 **/

/**
 *@Author:759057893@qq.com Lyz
 *@Date: 2019/6/23 17:45
 *@Description:
 **/

/*
编写一个程序，找到两个单链表相交的起始节点。

解题思路: 1.先求出两个链表分别的长度，然后长度做减法运算
2，如果A -B > 0 说明A链表长于B链表， 则让A链表先往前移动(A-B)步，这样A和B就保持到同一起点位置
然后比较同一起点位置是否相同，如果不相同，让两个链表保持前进，直到相同为止。
3 如果A -B < 0 说明A链表短于B链表， 则让B链表先往前移动(A-B)步，这样A和B就保持到同一起点位置
然后比较同一起点位置是否相同，如果不相同，让两个链表保持前进，直到相同为止。

 */
public class Test23 {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB){
        if(headA==null&& headB==null){
            return  null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;

        int countA = 0 ;
        int countB =0;
        while(p1!=null){
            p1 = p1.next;
            countA++;
        }
        while(p2!=null){
            p2 = p2.next;
            countB++;
        }
        int flag = countA - countB;
        if(flag>0){
            while (flag>0){
                headA = headA.next;
                flag--;
            }
            while(headA!=headB){
                headA =headA.next;
                headB = headB.next;
            }
            return  headA;
        }
        if(flag<=0){
            while (flag<0){
                headB = headB.next;
                flag++;
            }
            while(headA!=headB){
                headA =headA.next;
                headB = headB.next;
            }
            return  headA;
        }
    return null;
    }
}
